program bm_14;

{$APPTYPE CONSOLE}

 var gs:array[0..255]of integer;
     bc:array['a'..'z']of integer;
     suff:array[0..255]of integer;

  function MAX(a,b:integer):integer;
    begin
      if a>b then result := a
        else result := b;
    end;


 procedure OUTPUT(T,p:string;ofset:integer);
   begin
     writeln(T);
     while ofset >1 do begin
                         write(' ');
                         dec(ofset);
                       end;
     writeln(p);
   end;



  procedure pre_bc(p:string);
      var i,m:integer;
          j:char;
    begin
      m := length(p);
      for j:='a' to 'z' do
        bc[j] := m;
      for i:=1 to m - 1 do
        bc[p[i]]:= m - i + 1;
    end;

  procedure sufixes(p:string);
      var i,f,g,m:integer;
    begin
      m := length(p);
      suff[m] := m;
      g := m;
      for i:=m-1 downto 1 do
        begin
          if (i>g)and(suff[i + m - f]<i - g) then suff[i] := suff[i + m - f]
            else begin
                   if (i<g) then g := i;
                   f := i;
                   while (g>0)and(p[g] = p[g+m-f]) do dec(g);
                   suff[i] := f - g;
                 end;

        end;
    end;

  procedure pre_gs(p:string);
      var i,j,m:integer;
    begin
      m:= length(p);

      sufixes(p);

      for i:=1 to m do gs[i] := m - 1;

      j :=1;

      i:=m;
      while i>0 do
       begin
         if (i = 0) or (suff[i] = i + 1) then
           while (j <m - i - 1) do begin
                                    if (gs[j] = m) then
                                    gs[j] := m - 1 - i;
                                    inc(i);
                                   end;
         dec(i);
       end;

      for i:=1 to m - 1 do
      gs[m  - suff[i]] := m - i;
    end;

    procedure bm(T,p:string);
        var n,m,i,j:integer;
      begin
        pre_bc(p);
        pre_gs(p);

        n := length(T);
        m := length(p);

        j:=0;

        while (j <= n - m + 1) do
          begin
            OUTPUT(T,p,j);
            i := m;
            while (i>0)and(p[i] = T[i + j - 1]) do dec(i);
            if (i<1) then begin
                            writeln('==== Solve : =============');
                            OUTPUT(T,p,j);
                            writeln('==========================');
                            inc(j,gs[1]);
                          end else inc(j,MAX(gs[i],bc[T[i+j]] - m + 1 + i));
          end;
      end;

begin

  bm('gagsdgcagagagdasdagcagagagdsf','gcagagag');
  readln;

end.
